/*
 * @lc app=leetcode.cn id=148 lang=typescript
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function sortList(head: ListNode | null): ListNode | null {
  if (head === null) return head;
  // 节点的数量
  let n = 0;
  let p = head;
  while (p) {
    p = p.next;
    n++;
  }

  const merge = (head: ListNode | null, n: number): ListNode | null => {
    if (n <= 1) return head;
    let lCount = n >> 1;
    let rCount = n - lCount;

    let p = head;
    // 找到左边的最后一个节点，需要将左右分开
    for (let i = 1; i < lCount; i++) {
      p = p.next;
    }
    let lNode = head;
    let rNode = null;
    // 分成左右2组节点
    rNode = p.next;
    p.next = null;

    // 分治
    lNode = merge(lNode, lCount);
    rNode = merge(rNode, rCount);

    // 合并
    const dumpy = new ListNode();
    p = dumpy;
    while (lNode || rNode) {
      if (rNode === null || (lNode && lNode.val <= rNode.val)) {
        p.next = lNode;
        p = p.next;
        lNode = lNode.next;
      } else {
        p.next = rNode;
        p = p.next;
        rNode = rNode.next;
      }
    }
    return dumpy.next;
  };

  return merge(head, n);
}
// @lc code=end
